public class KMP {

	public String currentString;
	public String patt;
	public int[] Bprime;
	public int[] B;
	
	public KMP(String current, String pat)
	{
		if(pat.length() == 0)
		{
			System.out.println("must have a pattern of length > 0. Didnt make a KMP, so expect null-pointers.");
			return;
		}
		currentString = current;
		patt = pat;
		B = new int[patt.length()];
		Bprime = new int[patt.length()+1];
		B = B();
		Bprime = Bprime();
	}
	
	public void mainz()
	{
		int[] ret;
		int i = 1;
		int j = 1;
		while(i <= (currentString.length()-patt.length()+j) )
		{
			ret = match(i,j,patt.length());
			
			i = ret[0];
			j = ret[1];

			if(j == patt.length()+1)
			{
				System.out.println("match at:"+(i-patt.length()));
			}
			if(j == 1)
			{
				i = i + 1;
			}
			else
			{
				j = Bprime[j-1];
			}
		} 
	}
	
	public int[] B()
	{
		int b = 0;
		B[0] = 0;
		for(int i = 0;i<patt.length()-1;i++)
		{
			b = B[i];
			while(b > 0 && patt.charAt(i+1) != patt.charAt(b+1))
			{
				b = B[b-1];
			}
			if(patt.charAt(i+1) == patt.charAt(b)) //det er i+1 og bare b, da i algoritmen har vi i starter p� 1 og b starter p� 0. Her starter begge p� 0.
			{
				B[i+1] = b+1;
			}
			else
			{
				B[i+1] = 0;
			}
		}
		return B;
	}
	
	public int[] Bprime()
	{
		Bprime[0] = 0;
		for(int j = 1;j<B.length+1;j++)
		{
			Bprime[j] = B[j-1]+1;
		}
		return Bprime;
	}
	
	public int[] match(int i, int j, int m)
	{
		int[] retArray = new int[2];
		while( j <= m && currentString.charAt(i-1) == patt.charAt(j-1))
		{
			i = i + 1;
			j = j + 1;
		}
		retArray[0] = i;
		retArray[1] = j;
		return retArray;
	}
	
}
